#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <set>
using namespace std;

typedef vector< vector<string> > Data;

#define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
#define pb push_back

const size_t maxTreeHeight = 7;

const bool use[] = {
false, // 0 : RefId
false, // 1 : IsBadBuy
false, // 2 : PurchDate
true, // 3 : Auction
false, // 4 : VehYear
true, // 5 : VehicleAge
false, // 6 : Make
false, // 7 : Model
false, // 8 : Trim
false, // 9 : SubModel
true, // 10 : Color
true, // 11 : Transmission
false, // 12 : WheelTypeID
true, // 13 : WheelType
true, // 14 : VehOdo
true, // 15 : Nationality
true, // 16 : Size
true, // 17 : TopThreeAmericanName
false, // 18 : MMRAcquisitionAuctionAveragePrice
false, // 19 : MMRAcquisitionAuctionCleanPrice
false, // 20 : MMRAcquisitionRetailAveragePrice
false, // 21 : MMRAcquisitonRetailCleanPrice
false, // 22 : MMRCurrentAuctionAveragePrice
false, // 23 : MMRCurrentAuctionCleanPrice
false, // 24 : MMRCurrentRetailAveragePrice
false, // 25 : MMRCurrentRetailCleanPrice
true, // 26 : PRIMEUNIT
true, // 27 : AUCGUART
false, // 28 : BYRNO
false, // 29 : VNZIP1
true, // 30 : VNST                      
true, // 31 : VehBCost
false, // 32 : IsOnlineSale
true  // 33 : WarrantyCost
};

int nodes;

int R() {
  return ((rand() & 32767) << 15) + (rand() & 32767);
}

vector<bool> isNumber;

int toInt( const string& s ) {
  int res = 0;
  forn( i, s.length() )
    res = res * 10 + s[i] - '0';
  return res;
}

class DecisionTree {
public:
  vector<DecisionTree*> children;
  double answer;
  int paramId;
  int separator;
  vector<string> paramValues;

  DecisionTree() {
    answer = -1;
  }

  double classify( const vector<string>& v ) {
    if ( answer > -0.5 ) return answer;
    if ( isNumber[paramId] )
      return children[ toInt( v[paramId] ) >= separator ]->classify( v );

    for ( size_t i = 0; i < paramValues.size(); i++ )
      if ( paramValues[i] == v[paramId] )
        return children[i]->classify( v );
    return 0.12;
  }
};

bool isPositiveNumber( const string& s ) {
  forn( i, s.length() )  
    if ( s[i] < '0' || s[i] > '9' ) return false;
  return true; 
}

vector<size_t> vv;

double getCategoricalIG( const Data& data, int id ) {
   map<string,int> values, total;
   int bad = 0;

   forn( j, data.size() ) {
     values[ data[j][id] ] += data[j][1][0] - '0';
     total[ data[j][id] ]++;
     bad += data[j][1][0] - '0';
   }
   if ( values.size() == 1 ) return -1;

     map<string,int>::iterator itv = values.begin();
     map<string,int>::iterator itt = total.begin();
     double sum = 0;
     double splitinfo = 0;
     for ( ; itv != values.end(); itv++, itt++ ) {
       double pj = itv->second * 1.0 / itt->second;
       if (pj < 1 && pj > 0)
         sum += itt->second * 1.0 / data.size() * (pj * log( pj ) + ( 1-pj ) * log( 1-pj )); // non-base-2 log, and no minus!
       pj = itt->second * 1.0 / data.size();
       splitinfo -= pj * log( pj );
     }
     double pj = bad * 1.0 / data.size();
     sum = -pj * log( pj ) - (1-pj) * log( 1-pj ) + sum; // -( -sum ) actually;
     sum /= splitinfo;
     return sum;
}

double entropy(int good, int total) {
  if (!total) return 0.0;
  double x = 0;
  if (good > 0) x -= 1.0*good/total*log(1.0*good/total);
  if (total-good > 0) x -= 1.0*(total-good)/total*log(1.0*(total-good)/total);
  return x;
}

double getRealValuedIG( const Data& data, int id, int& separator, bool printRes = false ) {
  int n = data.size(), i;
  vector < pair <int,int> > z( n );
  for (i=0;i<n;i++) z[i] = make_pair(toInt(data[i][id]),data[i][1][0]-'0');
  sort(z.begin(),z.end());
  if ( z.back().first < z.front().first * 2.2 ) return -0.5;
  z.push_back(make_pair((int)1e9,1));
  int c = 0, s = 0;
  for (i=0;i<n;i++) s += z[i].second;
  double minE = -1e9;
  double H = entropy(s,n);
  for (i=0;i<=n;i++) {
    double x = H - (i*entropy(c,i)+(n-i)*entropy(s,n-i))/n;
    x /= entropy(i,n);
    if (i > 0 && i < n && z[i-1].first < z[i].first && x > minE) {
      minE = x;
      separator = z[i].first;
    }
    if (i == n) break;
    if (z[i].second == 1) c++, s--;
  }
//  if ( printRes ) fprintf( stderr, "IG from %d is %.5f\n", id, minE );
  return minE;
}

DecisionTree* buildDecisionTree( const Data& data, size_t m, size_t h ) {
  nodes++;
  DecisionTree* res = new DecisionTree();
  double maxIG = 0;
  int maxIGind = -1, maxSep = -1;
//  vector<size_t> vv;
//  for ( size_t i = 2; i < data[0].size(); ++i )
//    if ( !isPositiveNumber( data[0][i] ) && i !=  )
//      vv.pb( i );

  random_shuffle( vv.begin(), vv.end() );

  int bad = 0;
  forn( i, data.size() )
    bad += data[i][1][0] - '0';

  if ( bad == (int)data.size() || bad == 0 ) {
    res->answer = bad > 0;
    return res;
  }
 
  size_t lim = min( m, vv.size() );
  if ( h > maxTreeHeight ) lim = 0;
  forn( qid, lim ) {
      int id = vv[qid]; 
      double z;
      int x;
      if ( isNumber[id] ) z = getRealValuedIG( data, id, x, h == 0 );
      else z = getCategoricalIG( data, id );

      if ( z > maxIG ) {
        maxIG = z;
        maxIGind = id;
        maxSep = x;
      }
  }

  if ( maxIGind == -1 ) {
    if ( h == 0 ) { fprintf( stderr, "->" ); forn( qid, lim ) fprintf( stderr, " %d", vv[qid] ); fprintf( stderr, "\n" ); }
    int bad = 0;
    forn( i, data.size() )
      bad += data[i][1][0] - '0';
    res->answer = bad * 1.0 / data.size();
    return res;
  }

  res->paramId = maxIGind;
  Data next;

  if ( isNumber[maxIGind] ) {
    res->separator = maxSep;
    next.clear();
    forn( i, data.size() )
      if ( toInt( data[i][maxIGind] ) < maxSep )
        next.pb( data[i] );
    res->children.pb( buildDecisionTree( next, m, h+1 ) );

    next.clear();
    forn( i, data.size() )
      if ( toInt( data[i][maxIGind] ) >= maxSep )
        next.pb( data[i] );
    res->children.pb( buildDecisionTree( next, m, h+1 ) );

    return res;
  }

  set<string> ss;
  forn( j, data.size() )
    ss.insert( data[j][maxIGind] );

  for ( set<string>::iterator it = ss.begin(); it != ss.end(); it++ ) {
    next.clear();
    forn( i, data.size() )
      if ( data[i][maxIGind] == *it )
        next.pb( data[i] );
    res->children.pb( buildDecisionTree( next, m, h+1 ) );
  }

  res->paramValues = vector<string>( ss.begin(), ss.end() );

  return res;
}